package com.llb666.java.leetcode;

import java.util.Arrays;

/**
 * 统计所有小于非负整数 n 的质数的数量。
 * Created by 斌~
 * 2021/4/16 14:36
 * @author mac
 */
public class 统计质数个数 {
    /**
     * 暴力算法优化  j*j < i   ------>原因： 2*3 与 3*2判定重复，i开根号可以减少遍历次数
     * @param n 非负整数 n
     * @return int
     */
    public static int countPrimes(int n) {
        int res = 0;

        for (int i = 2; i <= n; i++) {
            boolean flag =true;
            for (int j = 2; j*j <= i; j++) {
                if (i % j == 0) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
//                System.out.println(i+",");
                res++;
            }
        }
        return res;
    }

    /**
     * 埃筛法
     * @param n 非负整数 n
     * @return int
     */
    public static int countPrimes2(int n) {
        boolean[] isPrim = new boolean[n];
        Arrays.fill(isPrim, true);
        for (int i = 2; i * i < n; i++) {
            //假如为true,为质数
            if (isPrim[i]) {
                //计算出所有与质数i相关的非质数并标记
                for (int j = i * i; j < n; j+=i) {
                    isPrim[j] = false;
                }
            }
        }
        int cnt = 0;
        for (int i = 2; i < n; i++) {
            if (isPrim[i]) {
                cnt++;
            }
        }
        return cnt;
    }
    public static void main(String[] args) {
//        System.out.println(countPrimes(100));
//        System.out.println(countPrimes2(100));
//        System.out.println(countPrimes2(499979));
        System.out.println(countPrimes3(39999));
        System.out.println(countPrimes2(39999));
        System.out.println(Integer.MAX_VALUE);
    }


    //java.lang.ArrayIndexOutOfBoundsException 数组下标越界
    public static int countPrimes3(int n) {
        int cnt = 0;
        boolean[] isPrim = new boolean[n];

        for (int i = 2; i < n; i++) {
            //假如为true,为质数
            if (!isPrim[i]) {
                cnt++;
                //计算出所有与质数i相关的非质数并标记
                for (int j = i * i; j < n; j+=i) {
                    try{
                        isPrim[j] = true;
                    }catch (ArrayIndexOutOfBoundsException e){
                        e.printStackTrace();
                        return j;
                    }
                }
            }
        }
        return cnt;
    }
}
